package NO21;

import java.util.Stack;

/**
 *  定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
 *  在该栈中，调用min、push 及pop的时间复杂度都是0(1)
 * @author swg
 *
 */

public class MinStack {
	
	private Stack<Integer> dataStack = new Stack<>();
	
	private Stack<Integer> minStack = new Stack<>();
	
	public void push(int node){
		//node直接放进dataStack中
		dataStack.push(node);
		//如果minStack为空或者node小于他的栈顶的值，就插入，否则再插一遍栈顶值（保证minStack记录的是当前已插入的序列的最小值）
		if(minStack.isEmpty() || node < minStack.peek()){
			minStack.push(node);
		}else{
			minStack.push(minStack.peek());
		}
	}
	
	//两个都要pop
	//假设push的是  4 2 5 1 3
	//minStackpush的是4 2 2 1 1
	//dataStack每个元素对应位置的minStack的元素，是其之前（包括自身）最小的元素
	public void pop(){
		dataStack.pop();
		minStack.pop();
	}
	
	//返回输入数据的栈顶元素
	public int top(){
		return dataStack.peek();
	}
	
	//返回输入数据的最小值
	public int min(){
		return minStack.peek();
	}
	
	public static void main(String[] args) {
		
	}
}
